package Red_Black_Tree;

/*
 * This is an implementation of Red-Black tree (RBTree).  RBTree is an important balanced binary search tree.
 * It's a little tricky in this implementation that this tree class is not to instance a new node by now.
 * User need to instance new nodes then pass the new node to the tree.
 */

public abstract class RBTree {

	protected Node root, leaf;
	
	/*
	 * When first constructing a RBTree, build a leaf node for all leaves.
	 * This is implemented in the subclasses.
	 * After this, other building work is done by inserting new nodes to it.
	 * ALSO: for a leaf, the parent pointer is always null
	 */	
	public RBTree(){
		root = null;
	}
	
	/*
	 * Insertion of this tree.
	 * It takes two steps: first insert the new node to the binary search tree as usual
	 *                     second relabel this tree to make it balance.
	 * 
	 * In the following, N stands for current node to be inserted;
	 *                   P stands for parent of current node;
	 *                   U stands for N's uncle;
	 *                   G stands for N's grandparent
	 */
	public void insert(Node N){
		binaryInsert(N);
		relabel_case1(N);
	}
	
	/*
	 * Conduct binary search on the tree to find the leaf node that 
	 * this new node should be inserted, then insert it.  
	 * Search starts from root node.
	 */
	protected void binaryInsert(Node n){
		
		if(root == null){
			root = n;
			
			root.setParent(null);
			root.setLChild(leaf);
			root.setRChild(leaf);
		}
		else{
			Node P = queryOnLastLevel(n);
			
			n.setParent(P);
			n.setBothChildrenLeaf(leaf);
			if(n.compareTo(P) <= 0)
				P.setLChild(n);
			else
				P.setRChild(n);

		}
	}
	
	/*
	 * For a new node, this method locates which position should it be on the last level.
	 * Input: a Node n.
	 * Output: the node on the last level that n should append. 
	 */
	public Node queryOnLastLevel(Node n){
		Node P = root;
		boolean reachLeaf = false;
		while(!reachLeaf){
			if(n.compareTo(P) <= 0 && !P.getLChild().equals(leaf))
				P = P.getLChild();
			else if (n.compareTo(P) > 0 && !P.getRChild().equals(leaf))
				P = P.getRChild();
			else
				reachLeaf = true;
		}
		
		return P;
	}
	
	/*
	 * These methods relabels current inserted node, possibly change order of some node,
	 * to maintain properties of a red-black tree.
	 */
	/*
	 * Case 1: Current node N is at the root of the tree
	 */
	protected void relabel_case1(Node N){
		if(N.getParent() == null)
			N.setBlack();
		else
			relabel_case2(N);
	}
	/*
	 * Case 2: Current node's parent P is black, nothing to do
	 */
	protected void relabel_case2(Node N){
		if(!N.getParent().isRed());
		else
			relabel_case3(N);
	}
	/*
	 * Case 3: Both parent P and uncle U are red
	 */
	protected void relabel_case3(Node N){
		Node U = N.getUncle();
		Node G = N.getGrandparent();
		
		//if((U != null && !U.equals(leaf)) && U.isRed()){
		if(U != null && U.isRed()){
			N.getParent().setBlack();
			U.setBlack();
			G.setRed();
			relabel_case1(G);
		}
		else
			relabel_case4(N);
	}
	/*
	 * Case 4: The parent P is red but the uncle U is black
	 */
	protected void relabel_case4(Node N){
		Node G = N.getGrandparent();
		Node P = N.getParent();
		
		if(N.equals(P.getRChild()) && P.equals(G.getLChild())){
			rotateLeft(P);
			N = N.getLChild();
		}
		else if(N.equals(P.getLChild()) && P.equals(G.getRChild())){
			rotateRight(P);
			N = N.getRChild();
		}
		
		relabel_case5(N);
	}
	/*
	 * Case 5: 
	 */
	protected void relabel_case5(Node N){
		Node G = N.getGrandparent();
		Node P = N.getParent();
		
		P.setBlack();
		G.setRed();
		if(N.equals(P.getLChild()) && P.equals(G.getLChild()))
			rotateRight(G);
		else if(N.equals(P.getRChild()) && P.equals(G.getRChild()))
			rotateLeft(G);
		else
			System.out.println("RBTree: Errer in case 5 !");
	}
	
	protected void rotateRight(Node n){
		Node p = n.getParent();
		Node lc = n.getLChild();
		
		//if(p == null) {
		if(n.equals(root)){
			root = lc;
			lc.setParent(null);
		}
		else if(n.equals(p.getLChild())){
			p.setLChild(lc);
			lc.setParent(p);
		}
		else if(n.equals(p.getRChild())){
			p.setRChild(lc);
			lc.setParent(p);
		}
		else
			System.out.println("RBTree error in rotate Right !");
		
		n.setLChild(lc.getRChild());
		lc.getRChild().setParent(n);
		lc.setRChild(n);
		n.setParent(lc);
	}
	
	protected void rotateLeft(Node n){
		Node p = n.getParent();
		Node rc = n.getRChild();
		
		//if(p == null) {
		if(n.equals(root)){
			root = rc;
			rc.setParent(null);
		}
		else if(n.equals(p.getLChild())){
			p.setLChild(rc);
			rc.setParent(p);
		}
		else if (n.equals(p.getRChild())) {
			p.setRChild(rc);
			rc.setParent(p);
		}
		else
			System.out.println("RBTree: error in rotate Left !");
		
		n.setRChild(rc.getLChild());
		rc.getLChild().setParent(n);
		rc.setLChild(n);
		n.setParent(rc);
	}
	
//	protected void rotateLeft(Node n){
//		Node y = n.getRChild();
//		n.setRChild(y.getLChild());
//		y.getLChild().setParent(x);
//	}
}














